package main

import "fmt"

func trap(height []int) int {
	// 左边最大值数组
	leftMaxArr := make([]int, len(height))
	leftMax := 0
	for i := 0; i < len(height); i++ {
		if leftMax < height[i] {
			leftMax = height[i]
		}
		leftMaxArr[i] = leftMax
	}

	// 右边最大值数组
	rightMaxArr := make([]int, len(height))
	rightMax := 0
	for i := len(height) - 1; i >= 0; i-- {
		if rightMax < height[i] {
			rightMax = height[i]
		}
		rightMaxArr[i] = rightMax
	}

	// 遍历数组,求每个柱子能存储的雨水
	area, minHeight := 0, 0
	for i := 0; i < len(height); i++ {
		if rightMaxArr[i] < leftMaxArr[i] {
			minHeight = rightMaxArr[i]
		} else {
			minHeight = leftMaxArr[i]
		}
		current := minHeight*1 - height[i]
		if current > 0 {
			area += current
		}
	}

	return area
}

func main() {

	nums := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	res := trap(nums)
	fmt.Println(res)
}
